package com.shexianyu.difficult;

import java.util.Arrays;

/**
 * 786. 第 K 个最小的素数分数
 */
public class KthSmallestPrimeFraction {

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        //存储结果数组
        int[] res = new int[2];
        //计算数组中总的计算分数的次数
        int sum = 0;
        for (int i = 1; i < arr.length; i++) {
            sum += i;
        }
        //声明数组存储计算分数的结果
        float[] value = new float[sum];
        int s = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                float val1 = arr[i];
                float val2 = arr[j];
                float val = val1 / val2;
                //将计算值存入数组中
                value[s] = val;
                s++;
            }
        }
        //将值数组进行排序
        Arrays.sort(value);
        //根据k找出对应值数组中的值
        float v = value[k - 1];
        //循环判断与v对应的匹配的值，用结果数组记录被除数与除数的下标
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                float val1 = arr[i];
                float val2 = arr[j];
                float val = val1 / val2;
                if (val == v) {
                    res[0] = arr[i];
                    res[1] = arr[j];
                }
            }
        }
        return res;
    }
}
